import { Vector3 } from "../utils/Math";

/**
 * 三维AABB包围盒
 */
export class AABB3D {
    min: Vector3;
    max: Vector3;
    constructor(min: Vector3, max: Vector3) {
        this.min = min;
        this.max = max;
    }
    /** 判断两个AABB是否相交 */
    static intersects(a: AABB3D, b: AABB3D): boolean {
        return a.max.x >= b.min.x && a.min.x <= b.max.x &&
               a.max.y >= b.min.y && a.min.y <= b.max.y &&
               a.max.z >= b.min.z && a.min.z <= b.max.z;
    }
    /** 由点集生成AABB */
    static fromPoints(points: Vector3[]): AABB3D {
        let minX = points[0].x, minY = points[0].y, minZ = points[0].z;
        let maxX = points[0].x, maxY = points[0].y, maxZ = points[0].z;
        for (const p of points) {
            if (p.x < minX) minX = p.x;
            if (p.x > maxX) maxX = p.x;
            if (p.y < minY) minY = p.y;
            if (p.y > maxY) maxY = p.y;
            if (p.z < minZ) minZ = p.z;
            if (p.z > maxZ) maxZ = p.z;
        }
        return new AABB3D(new Vector3(minX, minY, minZ), new Vector3(maxX, maxY, maxZ));
    }
}

/**
 * 八叉树节点（支持动态插入/删除，便于复用）
 */
export class OctreeNode {
    center: Vector3;
    halfSize: number;
    objects: { position: Vector3, radius: number, id: number }[] = [];
    children: OctreeNode[] | null = null;
    maxObjects: number;
    maxDepth: number;
    depth: number;
    constructor(center: Vector3, halfSize: number, maxObjects = 8, maxDepth = 6, depth = 0) {
        this.center = center;
        this.halfSize = halfSize;
        this.maxObjects = maxObjects;
        this.maxDepth = maxDepth;
        this.depth = depth;
    }
    /** 插入对象 */
    insert(obj: { position: Vector3, radius: number, id: number }) {
        if (this.children) {
            const idx = this.getChildIndex(obj.position);
            this.children[idx].insert(obj);
            return;
        }
        this.objects.push(obj);
        if (this.objects.length > this.maxObjects && this.depth < this.maxDepth) {
            this.subdivide();
            for (const o of this.objects) {
                const idx = this.getChildIndex(o.position);
                this.children![idx].insert(o);
            }
            this.objects = [];
        }
    }
    /** 查询某个范围内的所有对象id */
    queryRange(center: Vector3, range: number, result: number[] = []) {
        // 如果不相交则直接返回
        if (!this.intersects(center, range)) return result;
        for (const o of this.objects) {
            if (o.position.distance(center) <= range + o.radius) {
                result.push(o.id);
            }
        }
        if (this.children) {
            for (const child of this.children) {
                child.queryRange(center, range, result);
            }
        }
        return result;
    }
    /** 判断节点是否与球体相交 */
    private intersects(center: Vector3, range: number): boolean {
        let d = 0;
        for (const k of ['x', 'y', 'z'] as const) {
            const min = (this.center[k] as number) - this.halfSize;
            const max = (this.center[k] as number) + this.halfSize;
            if ((center[k] as number) < min) d += ((center[k] as number) - min) ** 2;
            else if ((center[k] as number) > max) d += ((center[k] as number) - max) ** 2;
        }
        return d <= range * range;
    }
    /** 获取点属于哪个子节点 */
    private getChildIndex(pos: Vector3): number {
        let idx = 0;
        if (pos.x >= this.center.x) idx |= 1;
        if (pos.y >= this.center.y) idx |= 2;
        if (pos.z >= this.center.z) idx |= 4;
        return idx;
    }
    /** 子节点划分 */
    private subdivide() {
        this.children = [];
        const hs = this.halfSize / 2;
        for (let dx = 0; dx <= 1; dx++) {
            for (let dy = 0; dy <= 1; dy++) {
                for (let dz = 0; dz <= 1; dz++) {
                    const cx = this.center.x + (dx ? hs : -hs);
                    const cy = this.center.y + (dy ? hs : -hs);
                    const cz = this.center.z + (dz ? hs : -hs);
                    this.children.push(new OctreeNode(new Vector3(cx, cy, cz), hs, this.maxObjects, this.maxDepth, this.depth + 1));
                }
            }
        }
    }
}

/**
 * 八叉树，支持插入和邻域查询
 */
export class Octree {
    root: OctreeNode;
    constructor(center: Vector3, halfSize: number, maxObjects = 8, maxDepth = 6) {
        this.root = new OctreeNode(center, halfSize, maxObjects, maxDepth);
    }
    insert(obj: { position: Vector3, radius: number, id: number }) {
        this.root.insert(obj);
    }
    queryRange(center: Vector3, range: number): number[] {
        return this.root.queryRange(center, range);
    }
} 